package com.scheuk.euler;

import java.util.ArrayList;  
import java.util.Iterator;  
import java.util.List;  
  

public class Sieve {  
  
    public static void main(String[] args) {  
          
        /* small test */  
    	long sT = System.currentTimeMillis();
        int[] primes = sieve(1, 1000);  
        long eT = System.currentTimeMillis();
        System.out.println("");
        for (int i : primes) {  
            System.out.println(i);  
        }  
    }  
      
    private static int[] sieve(int start, int end) {  
          
        /* some basic range checks */  
        if(start < 1 || end < start || start == end) {  
            throw new ArithmeticException("Messed up input");  
        }  
          
        /* generate ints within range */  
        int[] primes = new int[end-start+1];  
        for (int j = 0; j < end - start + 1; j++) {  
            primes[j] = start + j;  
        }  
          
        /* init running prime to start, and increment until 
         * running prime squared is greater than the end 
         */  
        for (int runningPrime = (start == 1 ? 2: start); end > Math.pow(runningPrime, 2); runningPrime++) {  
            for (int i = runningPrime; i < primes.length; i++) {  
                if(-1 != primes[i]) {  
                    if(primes[i] % runningPrime == 0) {  
                        primes[i] = -1;  
                    }  
                }  
            }  
        }  
          
        /* handling that twat */  
        if(primes[0] == 1) {  
            primes[0] = -1;  
        }  
          
        /* list primes */  
        List list = new ArrayList();  
        for (int i = 0; i < primes.length; i++) {  
            if(-1 != primes[i])  
                list.add(primes[i]);  
        }  
          
        /* create the return int array */  
        int[] primesFound = new int[list.size()];  
        int k = 0;  
        for (Iterator iterator = list.iterator(); iterator.hasNext();) {  
            //Integer i = (Integer) iterator.next();  
            //primesFound[k] = i.intValue();  
            //k++;  
            primesFound[k++] = ((Integer) iterator.next()).intValue();  
        }  
          
        return primesFound;  
    }  
}  
